单词搜索计数

题目内容

给定一个 $m \times n$ 的二维字符网格 board 和一个字符串单词 word。

请计算单词 word 在网格中出现的总次数。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个搜索路径中不允许被重复使用。

输入描述

• board：二维字符列表，每个元素为大写英文字母，$1 \le m,n \le 10$。
• word：字符串，由大写英文字母组成，$1 \le len(word) \le 100$。

输出描述

返回一个整数，表示单词在网格中出现的路径总数。

样例

样例 1

输入

ABCE SFCS ADEE
ABCCED

输出

1

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const bord = input.split(' ').map(v => v.split(''));
    rl.on('line', (word) => {
        const m = bord.length;
        const n = bord[0].length;
        let num = 0;
        const used = Array.from({length: m}, () => Array.from({length: n}, () => false));
        const temp = [[-1,0], [1,0], [0,-1], [0,1]];
        const dfs = (x, y, s) => {
            if (s === word) {
                num++;
                return;
            } else if (s.length > word.length) {
                return;
            }
            for(let i=0; i<temp.length; i++) {
                const nx = x + temp[i][0];
                const ny = y + temp[i][1];
                if (nx >=0 && nx < m && ny >=0 && ny < n && !used[nx][ny]) {
                    used[nx][ny] = true;
                    dfs(nx, ny, s+bord[nx][ny]);
                    used[nx][ny] = false;
                }
            }
        }
        for(let i=0; i<m; i++) {
            for(let j=0; j<n; j++) {
                if (bord[i][j] === word[0]) {
                    used[i][j] = true;
                    dfs(i, j, word[0]);
                    used[i][j] = false;
                }
            }
        }
        console.log(num);
    });
});